Today’s Agenda

  • Hausdorff Distance
  • Gromov–Hausdorff Distance
  • Hasudorff vs Gromov–Hausdorff
  • The curious case of the circle
  • Lower bounds
    • Riemannian manifolds
    • metric graphs
  • Future work

The Hausdorff Distance

Definition 1 (Directed Hausdorff Distance) For two subsets compact \(X,Y\subset\mathbb R^n\), their Hausdorff distance is \[ \vec{d}_H(X,Y)=\min\bigg\{r\geq0\mid X\subset \bigcup_{y\in Y} B(y,r)\bigg\}. \]

Definition 2 (Hausdorff Distance) \[ d_H(X,Y)=\max\bigg\{\vec{d}_H(X,Y),\vec{d}_H(Y,X)\bigg\}. \]

Why Only Euclidean Subsets?

Definition 3 (Hausdorff Distance) Let \((Z,d)\) be a metric space and \(X, Y\subset\) compact subsets. \[ \vec{d}^Z_H(X,Y)=\min\{r\geq0\mid X\subset \cup_{y\in Y} B(y,r)\}. \]

\[ d^Z_H(X,Y)=\max\bigg\{\vec{d}^Z_H(X,Y),\vec{d}^Z_H(Y,X)\bigg\}. \]

If \(Y=Z\), then \(d^Z_H(X,Z)=\vec{d}_H(Z,X)\).

\(S^1\) is the circle with circumference \(2\pi\)

\[ d_H(X,S^1)=\frac{\pi}{4}. \]

The Gromov–Hausdorff Distance

What if the subsets \(X,Y\) have no common embeddding?

Isometric embedding

\[ d_{GH}(X,Y)=\inf d^Z_H(f(X),g(Y)) \]

Some Properties and Results

  • \(d_{GH}(X,Y)=0\) if and only if \(X\), \(Y\) are isometric

  • \[\tfrac{1}{2}|diam(X)-diam(Y)|\leq d_{GH}(X,Y)\leq \tfrac{1}{2}\max\big\{diam(X), diam(Y)\big\}\]

  • When \(X, Y\) are finite metric spaces

    • Computationally feasible (distortion definition)
    • Minimization problem with exponential search space

  • If \(X,Y\) metric graphs, then \(NP\)-hard (A. Aggarawal et al.)

  • If \(X,Y\subset\mathbb{R}^1\), then \(\frac{5}{4}\)-approximable (Majhi et al.)

Hausdorff vs Gromov–Hausdorff

  • Let \((Z,d)\) be a metric space and \(X\subset Z\)
    • \(d^Z_H(X,Z)\) is well-defined
  • \((X,d)\) is also a metric space
    • \(d_{GH}(X,Z)\) can be defined

How the two distances \(d_{GH}(X,Z)\) and \(d^Z_H(X,Z)\) compare?

  • \(d_{GH}(X,Z)\leq d^Z_H(X,Z)\)

Comparison on the Circle

\[ d_H(X,S^1)=\frac{\pi}{2} \]

\[ \frac{1}{2}\pi\leq d_{GH}(X,S^1)\leq \frac{1}{2}\pi \implies d_{GH}(X,S^1)=\frac{\pi}{2} \]

Comparison on the Circle

\[ d_H(X,S^1)=\frac{\pi}{4} \]

\[ \frac{1}{2}0\leq d_{GH}(X,S^1)\leq \frac{1}{2}\pi \implies ? \]

\(d_{GH}(X,S^1)=d_H(X,S^1)\)

Comparison on the Circle

\[ \frac{\pi}{3}=d_{GH}(X,S^1)<d_{H}(X,S^1)=\frac{\pi}{3}+\varepsilon. \]

Optimal Density for the Circle

Theorem 1 (2023) For \(X\subset S^1\) with \(d_H(X,S^1)<\frac{\pi}{6}\), then \(d_{GH}(X,S^1)=d_H(X,S^1)\).

  • Proof is topological
  • Is \(\frac{\pi}{6}\) optimal?

Theorem 2 (2024) For \(X\subset S^1\) with \(d_H(X,S^1)<\frac{\pi}{3}\), then \(d_{GH}(X,S^1)=d_H(X,S^1)\).

  • Proof is purely geometric

Non-Trivial Lower Bounds

  • Intuition: when a sample becomes dense enough, it starts to capture the geometry of the space.

  • Circle: \(d_{GH}(X,S^1)\geq\min\big\{d_H(X, S^1),\frac{\pi}{3}\big\}\).

  • Generally: \(d_{GH}(X,Z)\geq\min\big\{\color{red}{C}\cdot d_H(X, Z), \color{red}{D}\big\}\)?

    • Cirlce: \(C=1\) and \(D=\frac{\pi}{3}\).

Theorem 3 (Bad News) For any \(C>0\), there exists a compact metric space \(Z\) and a subset \(X\subseteq Z\) with \(d_{GH}(X,Z) < C \cdot d_{H}(X,Z).\)

Good News

Theorem 4 (Closed Riemannian Manifolds) For \(X\subset M\), we have \[ d_{GH}(X,M)\geq\min\bigg\{\color{green}{\frac{1}{2}}d_H(X, S^1),\color{green}{\frac{2\rho}{3}}\bigg\}. \]

Metric Graphs

Questions

Thank you